#include <iostream>
#include <string>
using std::cout;
using std::endl;

struct Node {
  Node* left;
  Node* right;
  int key;
  std::string value;

  Node(int key_init, const std::string& value_init, Node* left_init = NULL,
       Node* right_init = NULL) {
    key = key_init;
    value = value_init;
    left = left_init;
    right = right_init;
  }
};

void Print(Node* node) { cout << node->key << ':' << node->value << ' '; }

typedef Node*& NodePtr;

// 没重复数据的二叉查找树/二叉排序树
class BinarySearchTree {
 public:
  BinarySearchTree() : root_(NULL) {}
  ~BinarySearchTree() {}

  void Insert(int key, const std::string& value) {
    Node* node = new Node(key, value);
    if (root_ == NULL) {
      root_ = node;
      return;
    }
    Node* p = root_;
    while (p) {
      if (key == p->key) {
        return;
      } else if (key < p->key) {
        if (p->left == NULL) {
          p->left = node;
          return;
        }
        p = p->left;
      } else {
        if (p->right == NULL) {
          p->right = node;
          return;
        }
        p = p->right;
      }
    }
  }

  Node* Search(int key) {
    Node* p = root_;
    while (p) {
      if (key == p->key) {
        return p;
      } else if (key < p->key) {
        p = p->left;
      } else {
        p = p->right;
      }
    }
    return NULL;
  }

  // 待删除节点B有三种情况
  // -有2个子节点：将右子节点的最小子节点(肯定没有左子节点)拷贝过来，然后删除那个子节点（转换成有0或1个子节点的删除问题）
  // -有1个子节点：只需将B的父节点(不为空时)指向B的子节点，再delete B
  // -没有子节点：只需将B的父节点(不为空时)指向NULL，再delete B
  void Delete(int key) {
    Node* parent = NULL;  // 父节点
    Node* p = root_;      // 当前节点
    // 查找待删除节点
    while (p) {
      if (key == p->key) {
        break;
      } else if (key < p->key) {
        parent = p;
        p = p->left;
      } else {
        parent = p;
        p = p->right;
      }
    }
    if (p == NULL) return;

    // 有2个子节点
    Node* target = p;
    if (p->left && p->right) {
      // 查找右子节点的最小子节点（也就是后继节点）
      parent = p;
      p = p->right;
      while (p->left) {
        parent = p;
        p = p->left;
      }
      // 拷贝
      target->key = p->key;
      target->value = p->value;
    }

    // 有0或1个子节点
    Node* child = NULL;
    if (p->left)
      child = p->left;
    else
      child = p->right;

    if (parent != NULL) {
      if (parent->left == p)
        parent->left = child;
      else
        parent->right = child;
    } else {
      root_ = child;
    }
    delete p;
  }

  void InOrder(Node* node) {
    if (node == NULL) return;
    InOrder(node->left);
    Print(node);
    InOrder(node->right);
  }

  int Height(Node* node) {
    if (node == NULL) return 0;
    return std::max(Height(node->left), Height(node->right)) + 1;
  }

  void PrintAll() {
    cout << "Height:" << Height(root_) << "  ";
    InOrder(root_);
    cout << endl;
  }

  Node* GetRoot() const { return root_; }

 private:
  Node* root_;
};

int main() {
  BinarySearchTree tree;
  tree.Insert(10, "hello");
  tree.Insert(4, "world");
  tree.Insert(6, "ni");
  tree.Insert(15, "hao");
  tree.Insert(12, "zhong");
  tree.Insert(20, "guo");
  tree.Insert(30, "yi");
  /*
      10
    4    15
     6  12 20
             30
  */
  tree.PrintAll();

  Node* node = tree.Search(12);
  if (node) {
    Print(node);
    cout << endl;
  }

  tree.Delete(15);
  /*
    10
  4    20
   6  12 30
  */
  tree.PrintAll();

  tree.Delete(4);
  /*
    10
  6    20
      12 30
  */
  tree.PrintAll();

  tree.Delete(30);
  /*
    10
  6    20
      12
  */
  tree.PrintAll();

  tree.Delete(10);
  /*
    12
  6    20
  */
  tree.PrintAll();
}